Masala #1215

Yangi yil kechasi yaqinlashmoqda va Qorbobo ustaxonasidagi elflar sovg'alarni qadoqlash uchun qizg'in ishlashmoqda! Ular oldida n ta sovg'a bor — har biri turli kattalikda va ularni qutilarga joylashtirish kerak. Har bir sovg'a bir xil oʻlchamdagi qutilarga joylanadi va \(i-\) sovg'ani sigʻdirish uchun quti hajmi kamida \(a_i\) boʻlishi lozim.

Elflar esa yirik sovg'alarni qutilarga joylashtirishni yoqtirishmaydi, ularning orzusi — eng kichik oʻlchamdagi qutilar ishlatish! Buning uchun ular bir sovg'ani ikkita butun qiymatli ikkita sovg'alarga boʻlib, har birini alohida qadoqlashlari mumkin. Ammo Qorbobo tartibni saqlash uchun faqat k marta bunday sehrli boʻlishga ruxsat bergan.

Elflarga yordam bering: berilgan sehrdan samarali foydalangan holda ishlatilishi mumkin bo'lgan eng kichik sovg'a qutisi o'lchamini aniqlang!

Kirish faylining birinchi qatorida ikkita butun son n va k beriladi — ustaxonadagi sovg'alar soni va maksimal ajratish (bo'lish) operatsiyalari soni.

Keyingi qatorda n ta butun son \(a_i\) — har bir sovg'a oʻlchamlari beriladi.

\(1 \le n \le 10^6\)

\(1 \le a_i \le 10^9\)

\(0 \le k \le 10^9\)

Sovg'alar uchun ishlatilishi mumkin bo'lgan qutining eng kichik hajmini chop eting.